package com.example.demo.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _73_矩阵置零 {

    public static void main(String[] args) {
        int[][] matrix1 = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        int[][] matrix2 = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        System.out.println(Arrays.deepToString(matrix1(matrix2)));
    }

    /**
     * 方法一：
     * 时间复杂度：O（n*m）
     * 空间复杂度：O(n*m)
     *
     * @param matrix
     * @return
     */
    public static int[][] matrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;

        int[][] temp = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                temp[i][j] = matrix[i][j];
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int element = matrix[i][j];
                if (element == 0) {
                    for (int k = 0; k < col; k++) {
                        temp[i][k] = 0;
                    }
                    for (int k = 0; k < row; k++) {
                        temp[k][j] = 0;
                    }
                }
            }
        }
        return temp;
    }

    /**
     * 方法二：
     * 时间复杂度:O(m*n)
     * 空间复杂度:O(m+n)
     *
     * @param matrix
     * @return
     */
    public static int[][] matrix1(int[][] matrix) {
        int rowMax = matrix.length;
        int colMax = matrix[0].length;

        List<Integer> rowList = new ArrayList<>();
        List<Integer> colList = new ArrayList<>();

        for (int row = 0; row < rowMax; row++) {
            for (int col = 0; col < colMax; col++) {
                int element = matrix[row][col];
                if (element == 0) {
                    rowList.add(row);
                    colList.add(col);
                }
            }
        }
        for (Integer row : rowList) {
            for (int i = 0; i < colMax; i++) {
                matrix[row][i] = 0;
            }
        }
        for (Integer col : colList) {
            for (int i = 0; i < rowMax; i++) {
                matrix[i][col] = 0;
            }
        }
        return matrix;
    }
}
